

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

using Node = TreeNode;

class Solution
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (!root)
            return nullptr;
        if (root == p)
            return p;
        if (root == q)
            return q;

        bool pInLeft = _InTree(root->left, p);
        bool pInRight = !pInLeft;
        bool qInLeft = _InTree(root->left, q);
        bool qInRight = !qInLeft;

        cout << root->val << endl;
        if (pInLeft && qInLeft)
            return lowestCommonAncestor(root->left, p, q);
        else if (pInRight && qInRight)
            return lowestCommonAncestor(root->right, p, q);
        else if ((pInLeft && qInRight) || (pInRight && qInLeft))
            return root;

        return nullptr;
    }

    vector<int> inorderTraversal(TreeNode* root)
    {
        if (!root)
            return {};

        vector<int> res;
        stack<Node*> st;
        Node* cur = root;

        while (cur || st.size())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            res.push_back(st.top()->val);

            cur = st.top()->right;
            st.pop();
        }

        return res;
    }

    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (!pRootOfTree)
            return nullptr;

        stack<Node*> st;
        Node* root = nullptr;
        Node* prev = nullptr, * cur = pRootOfTree;

        cur = pRootOfTree;
        while (cur)
        {
            prev = cur;
            cur = cur->left;
        }
        root = prev;

        int flag = 1;
        for (cur = pRootOfTree, prev = nullptr; cur || st.size();)
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            if (prev)
            {
                cur->left = prev;
                prev->right = cur;
            }

            prev = cur;
            cur = cur->right;
            st.pop();
        }

        return root;
    }

    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        if (1 == n)
            return nums[0];

        int res = INT_MIN;

        for (int i = 0; i < n; ++i)
        {
            int sum = 0;
            for (int j = i; j < n; ++j)
            {
                sum += nums[j];
                res = max(res, sum);
            }
        }

        return res;
    }

    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n)
    {
        int on = original.size();
        if (on != m * n)
            return {};

        vector<vector<int>> res;

        for (int i = 0, index = 0; i < m; ++i, index += n)
        {
            res.push_back({ original.begin() + index, original.begin() + index + n });
        }

        return res;
    }

    vector<string> findWords(vector<string>& words)
    {
        vector<string> res;
        vector<int> cnt1(58), cnt2(58), cnt3(58);
        string s1 = "qwertyuiop", s2 = "asdfghjkl", s3 = "zxcvbnm";

        Init(s1, cnt1);
        Init(s2, cnt2);
        Init(s3, cnt3);

        for (const auto& e : words)
        {
            int n = e.size();
            int flag1 = 0, flag2 = 0, flag3 = 0;

            for (auto ch : e)
            {
                if (cnt1[ch - 'A'] && !cnt2[ch - 'A'] && !cnt3[ch - 'A'])
                {
                    ++flag1;
                }
                else if (!cnt1[ch - 'A'] && cnt2[ch - 'A'] && !cnt3[ch - 'A'])
                {
                    ++flag2;
                }
                else
                {
                    ++flag3;
                }
            }

            if (flag1 == n || flag2 == n || flag3 == n)
                res.push_back(e);
        }

        return res;
    }

    int numJewelsInStones(string jewels, string stones)
    {
        int res = 0;
        vector<int> jew(58);

        for (const auto& e : jewels)
        {
            ++jew[e - 'A'];
        }
        for (const auto& e : stones)
        {
            if (jew[e - 'A'])
                ++res;
        }

        return res;
    }

    int foundOnceNumber(vector<int>& arr, int k)
    {
        int res = 0;

        for (int i = 0; i < 32; ++i)
        {
            int sum = 0;
            for (const auto& e : arr)
            {
                sum += (e >> i) & 1U;
            }
            if (sum %= k)
                res |= 1U << i;
        }

        return res;
    }

    char findTheDifference1(string s, string t)
    {
        char xorsum = 0;

        for (const auto& e : s)
        {
            xorsum ^= e;
        }
        for (const auto& e : t)
        {
            xorsum ^= e;
        }

        return xorsum;
    }

    char findTheDifference2(string s, string t)
    {
        char xorsum = 0;

        for (const auto& e : s + t)
        {
            xorsum ^= e;
        }

        return xorsum;
    }

    uint32_t reverseBits(uint32_t n)
    {
        int res = 0;

        for (int i = 0; i < 32; ++i)
        {
            res += (n & 1) * (1 << (31 - i));
            n >>= 1;
        }

        return res;
    }

    int countGoodSubstrings(string s)
    {
        int res = 0;
        int n = s.size();

        for (int i = 0; i < n - 2; ++i)
        {
            if (s[i] != s[i + 1] && s[i + 1] != s[i + 2] && s[i] != s[i + 2])
                ++res;
        }

        return res;
    }

    vector<string> uncommonFromSentences(string s1, string s2)
    {
        s1 += ' ';
        s2 += ' ';
        vector<string> res;
        unordered_set<string> hash;

        int beg = 0, pos = 0;
        int n1 = s1.size(), n2 = s2.size();

        for (beg = 0, pos = 0; pos < n1; )
        {
            pos = s1.find(' ', pos);
            hash.insert(s1.substr(beg, pos - beg));
            beg = ++pos;
        }

        for (beg = 0, pos = 0; pos < n2;)
        {
            pos = s2.find(' ', pos);

            string cur = s2.substr(beg, pos - beg);
            beg = ++pos;
            if (!hash.count(cur))
                res.push_back(cur);
        }

        return res;
    }

    vector<string> uncommonFromSentences(string s1, string s2)
    {
        vector<string> res;
        unordered_map<string, int> hash;

        _func(s1, hash);
        _func(s2, hash);

        for (const auto& e : hash)
        {
            if (1 == e.second)
                res.push_back(e.first);
        }

        return res;
    }

    string compressString(string S)
    {
        int n = S.size();
        if (!n)
            return S;

        string res;

        for (int beg = 0, end = 0; beg < n;)
        {
            for (end = beg; S[end] == S[beg]; ++end);
            res += S[beg];
            res += to_string(end - beg);
            beg = end;
        }

        return res.size() < n ? res : S;
    }

private:
    void _func(string& s, unordered_map<string, int>& hash)
    {
        s += ' ';
        for (int beg = 0, pos = 0, n = s.size(); pos < n; )
        {
            pos = s.find(' ', pos);
            ++hash[s.substr(beg, pos - beg)];
            beg = ++pos;
        }
    }

    void Init(string& s, vector<int>& v)
    {
        for (int i = 0, n = s.size(); i < n; ++i)
        {
            ++v[s[i] - 'A'];
            ++v[s[i] - 32 - 'A'];
        }
    }

    bool _InTree(Node* root, Node* cur)
    {
        stack<Node*> st;

        while (root || st.size())
        {
            while (root)
            {
                if (root == cur)
                    return true;
                st.push(root);
                root = root->left;
            }
            root = st.top()->right;
            st.pop();
        }

        return false;
    }
};

void Test1()
{
	class A
	{
	public:
		void foo()
		{
			printf("1");
		}

		virtual void fun()
		{
			printf("2");
		}
	};

	class B : public A
	{
	public:
		void foo()
		{
			printf("3");
		}

		void fun()
		{
			printf("4");
		}
	};

	A a;
	B b;
	A* p = &a;
	p->foo();
	p->fun();
	p = &b;
	p->foo();
	p->fun();
	A* ptr = (A*)&b;
	ptr->foo();
	ptr->fun();
}

vector<Node*> GetTree(void)
{
    Node* node3 = new Node(3);
    Node* node5 = new Node(5);
    Node* node1 = new Node(1);
    Node* node6 = new Node(6);
    Node* node2 = new Node(2);
    Node* node0 = new Node(0);
    Node* node8 = new Node(8);
    Node* node7 = new Node(7);
    Node* node4 = new Node(4);

    node3->left = node5, node3->right = node1;
    node5->left = node6, node5->right = node2;
    node1->left = node0, node1->right = node8;
    node2->left = node7, node2->right = node4;

    return {node3, node5, node4};
}

void Test2()
{
    vector<Node*> v = GetTree();
    Node* root = v[0], *p = v[1], *q = v[2];

    cout << Solution().lowestCommonAncestor(root, p, q)->val << endl;
}

void Test3()
{
    class CParent
    {
    public: 
        virtual void Intro()
        {
            printf("I'm a Parent, "); Hobby();
        } 

        virtual void Hobby()
        {
            printf("I like football!");
        }
    };

    class CChild : public CParent 
    {
    public: 
        virtual void Intro()
        {
            printf("I'm a Child, "); Hobby();
        }

        virtual void Hobby()
        {
            printf("I like basketball!\n");
        }
    };

    CChild* pChild = new CChild();
    CParent* pParent = (CParent*)pChild;
    pParent->Intro();
}

void Test4()
{
    string s = "00000010100101000001111010011100";

    cout << s << endl;
    reverse(s.begin(), s.end());
    cout << s << endl;
    cout << "00111001011110000010100101000000" << endl;
}

void Test5()
{
    Solution().uncommonFromSentences("this apple is sweet", "this apple is sour");
}

int main()
{
	Test1();
    Test2();
    Test3();
    Test4();
    Test5();

	return 0;
}